As one of techniques of acquiring two dimensional information of an object as a measurement target and reconstructing a three-dimensional shape of the object based on the two-dimensional information, there is a technique of reconstructing a three-dimensional shape of an object from multi-viewpoint videos. Reconstruction of the three-dimensional shape of an object from multi-viewpoint videos uses visual hull based on epipolar geometry (for example, see: Fujimoto Yuichiro et al., OpenCV 3 Programming Book, Mynavi Corporation, September 2015, ISBN-10:4839952965; Jan Erik Solem, translated by Aikawa Aizo, Programming Computer Vision with Python, O'Reilly Japan, Inc., March 2013, ISBN978-4-87311-607-5, Chapter 5 “5.1 Epipolar Geometry” and “5.2 Computing with Cameras and 3D Structure”; Mizuno Hiroki, Fujiyoshi Hironobu, and Iwahori Yuji, “A method for regularizing three dimensional scene flow by subspace constraints and estimating rigid motion”, The IEICE transactions on information and systems, Vol. J90-D, No. 8, pp. 2019-2027 (2007); and Deguchi Koichiro, Basis of Robot Vision, CORONA PUBLISHING CO., LTD., 2000).
In the visual hull, a line segment search for deriving a silhouette cone involves data accesses (oblique accesses) along the inclination of a line segment. The line segment searches are performed in P parallel processes, and are each carried out by: calculating storage locations of target pixels in the silhouette image area 107′ based on the position of the epipolar line found by the search; and reading the silhouette data [P] (see FIG. 19). The memory accesses to the silhouette image area 107′ involve accesses to non-consecutive data areas according to the inclination of the epipolar line.
Consecutive data areas are optimal as memory access locations for a usual processing system, but oblique access locations in a line segment search are non-consecutive data areas. The oblique accesses by a memory access unit 104′ illustrated in FIG. 19 are so largely affected by a memory latency (response delay time) that a response delay time occurs.
In the case of using a graphics processing unit (GPU) in the above processing, if the relation between threads to be processed in one batch (which is a unit called a warp in some GPUs) and data access locations follows a regular pattern, data access efficiency is high (called coalesce access in some GPUs). In contrast, when the processing by the GPU accesses non-consecutive data areas or accesses data in an irregular pattern, two or more accesses are made during 1 warp (such a memory access is called replay in some GPUs).
Moreover, the latency varies depending on a memory layer. A conceivable way to avoid an increase in the number of accesses to a memory with a long latency is to accumulate a group of frequently used data in a high-speed storage device. As a known example thereof, there is a method of improving a processing speed by cache hits (desired data is found in a cache and may be read) by limiting a memory space to be accessed (for example, see International Publication Pamphlet No. WO 2015/141549).